#include <cstdlib>
#include <map>
#include <cassert>
#include "inc.h"

// 计时器
/*
extern struct timeval cur_utime;
double get_utime() {
	gettimeofday(&cur_utime, NULL);
	return (double)cur_utime.tv_sec * 1000 + (double)cur_utime.tv_usec / 1000;
}
struct Stat {
	double total;
	int count;
};
Stat g_Stat[1000];
void add_stat(int key, double cost) {
	Stat& s = g_Stat[key];
	s.total += cost;
	s.count++;
}
void print_stat() {
	for (int i = 0; i < 1000; i++) {
		Stat& s = g_Stat[i];
		if (s.count > 0) {
			printf("[stat-%2d] count=%8d, avg=%10.6f(ms), total=%f\n", i, s.count, s.total/s.count, s.total);
		}
	}
}*/


// 内存池
class Node;
typedef std::map<uint32_t, Node*> NodeMap;

enum EnAoiEvent {
	FansEnter = 0,	// 进入fans的视野
	FansLeave,
	MarkEnter,		// mark进入自己的视野
	MarkLeave,
};

lua_State* g_AoiLua;
static bool g_AoiLock = false;
// #define AOI_LOCK { if (g_AoiLock) { traceback(L, "AOI_LOCK");} g_AoiLock = true; }
#define AOI_LOCK { if (g_AoiLock) g_AoiLock = true; }
#define AOI_UNLOCK { g_AoiLock = false; }

#define POS_TYPE_LEFT	1
#define POS_TYPE_MID	2
#define POS_TYPE_RIGHT	4

// 节点在轴线上的表示单位
struct Pos {
	int type;
	int value;
	Pos* pre;
	Pos* next;
	Node* owner;
};

class Node {
public:
	uint32_t id;
	int range;
	int smask;		// 自己的标签
	int imask;  	// 感兴趣的标签
	int center[2];	// 中心点
	Pos pos[6];		// 左、中、右、上、中、下 4个坐标点
	Node* next;

	NodeMap fans; 	// 关注我的人
	NodeMap mark; 	// 我关注的人
	NodeMap tmp[4];

public:
	Node(uint32_t _id, int _range, int _smask, int _imask, int x, int y): id(_id), range(_range), smask(_smask), imask(_imask), next(NULL) {
		center[0] = x;
		center[1] = y;
		pos[0].owner = pos[1].owner = pos[2].owner = this;
		pos[3].owner = pos[4].owner = pos[5].owner = this;
		pos[0].type = pos[3].type = POS_TYPE_LEFT;
		pos[1].type = pos[4].type = POS_TYPE_MID;
		pos[2].type = pos[5].type = POS_TYPE_RIGHT;
	}

	// save: true表示当前节点属于正在计算移动的点，需要缓存数据
	inline void on_enter(Node* target, bool save) {
		if (target->center[0] < center[0] - range 
		|| target->center[0] > center[0] + range 
		|| target->center[1] < center[1] - range
		|| target->center[1] > center[1] + range) { return; }
		if ((imask & target->smask) != 0) {
			if (add_mark(target, save)) {
				target->add_fans(this, !save);
			}
		}
		if ((smask & target->imask) != 0) {
			if (add_fans(target, save)) {
				target->add_mark(this, !save);
			}
		}
	}
	
	inline void on_leave(Node* target, bool save) {
		if ((imask & target->smask) != 0) {
			if (del_mark(target, save)) {
				target->del_fans(this, !save);
			}
		}
		if ((smask & target->imask) != 0) {
			if (del_fans(target, save)) {
				target->del_mark(this, !save);
			}
		}
	}
	inline bool add_fans(Node* target, bool save) {
		NodeMap::iterator it = fans.find(target->id);
		if (it != fans.end()) { return false; }
		fans.insert(NodeMap::value_type(target->id, target));
		if (save) {
			tmp[0].insert(NodeMap::value_type(target->id, target));
		}
		return true;
	}
	inline bool del_fans(Node* target, bool save) {
		NodeMap::iterator it = fans.find(target->id);
		if (it == fans.end()) { return false; }
		fans.erase(it);
		if (save) {
			tmp[1].insert(NodeMap::value_type(target->id, target));
		}
		return true;
	}
	inline bool add_mark(Node* target, bool save) {
		NodeMap::iterator it = mark.find(target->id);
		if (it != mark.end()) { return false; }
		mark.insert(NodeMap::value_type(target->id, target));
		if (save) {
			tmp[2].insert(NodeMap::value_type(target->id, target));
		}
		return true;
	}
	inline bool del_mark(Node* target, bool save) {
		NodeMap::iterator it = mark.find(target->id);
		if (it == mark.end()) { return false; }
		mark.erase(it);
		if (save) {
			tmp[3].insert(NodeMap::value_type(target->id, target));
		}
		return true;
	}
	
	// 清理其他单位对自己的引用
	inline bool clear_mark() {
		for (NodeMap::iterator it = fans.begin(); it != fans.end(); it++) {
			it->second->del_mark(this, false);
		}
	}
	inline bool clear_fans() {
		for (NodeMap::iterator it = mark.begin(); it != mark.end(); it++) {
			it->second->del_fans(this, false);
		}
	}
};

Node* g_PoolHead = NULL;
Node* CreateNode() {
	if (g_PoolHead == NULL) { return NULL; }
	Node* node = g_PoolHead;
	g_PoolHead = node->next;
	node->next = NULL;
	return node;
}
void ReleaseNode(Node* node) {
	if (!g_PoolHead) {
		node->next = g_PoolHead;
	}
	g_PoolHead = node;
}
void ReleaseAllNode() {
	Node* node = g_PoolHead;
	Node* next;
	while (node) {
		next = node->next;
		delete(node);
		node = next;
	}
	g_PoolHead = NULL;
}


class Scene {
public:
	int id;					// 场景的唯一编号
	int callback;
	bool isFixedRange;		// 是否统一视野
	Pos* head[2];			// 坐标轴的头节点
	NodeMap nodes;			// 所有节点集合, {[nodeId] = Node*}
	Scene(int _id, int _cb, bool _isFixed): id(_id), callback(_cb), isFixedRange(_isFixed) {
		head[0] = head[1] = NULL;
	}
	~Scene() {
		if (callback > 0) {
			luaL_unref(g_AoiLua, LUA_REGISTRYINDEX, callback);
			callback = 0;
		}
		for (NodeMap::iterator i = nodes.begin(); i != nodes.end(); i++) {
			ReleaseNode(i->second);
		}
		nodes.clear();
		head[0] = head[1] = NULL;
	}

	inline void check_neighbour(Pos* pos, Pos* target, int range, bool toRight) {
		if (pos->type & POS_TYPE_MID) {
			// pos进入target的视野
			if ((pos->owner->smask & target->owner->imask) == 0) { return; }

			if (target->type & POS_TYPE_LEFT) {
				if (toRight) {
					// mid向右移动越过左边界点
					if (pos->value > target->value + range + range) { return; }
					target->owner->on_enter(pos->owner, false);
				} else {
					// mid向左移动越过左边界点
					target->owner->on_leave(pos->owner, false);
				}
			} else {
				if (toRight) {
					// mid向右移动越过右边界点
					target->owner->on_leave(pos->owner, false);
				} else {
					// mid向左移动越过右边界点
					if (pos->value < target->value - range - range) { return; }
					target->owner->on_enter(pos->owner, false);
				}
			}
		} else {
			if ((pos->owner->imask & target->owner->smask) == 0) { return; }
			
			if (pos->type & POS_TYPE_LEFT) {
				if (toRight) {
					// left向右移动越过中心点
					pos->owner->on_leave(target->owner, true);
				} else {
					// left向左移动越过中心点
					if (target->value > pos->value + range + range) { return; }
					pos->owner->on_enter(target->owner, true);
				}
			} else {
				if (toRight) {
					// right向右移动越过中心点
					if (target->value < pos->value - range - range) { return; }
					pos->owner->on_enter(target->owner, true);
				} else {
					// right向左移动越过中心点
					pos->owner->on_leave(target->owner, true);
				}
			}
		}
	}

	// 将pos插入到link上最靠近目标点的位置上，pos是左边界点
	// 最靠近pos最终位置的，就是pos-range的点
	inline void link_add(int index, Pos* pos, int target, Pos* start) {
		Pos* cur = start;
		// TODO 这里是最耗时的地方
		if (start->value <= target) {
			// 目标点比start大，向右侧搜索
			while (cur->value < target) {
				if (!cur->next) { break; }
				cur = cur->next;
				assert(cur != cur->next);
			}
		} else {
			// 目标点比start小，向左侧搜索
			while (cur->value > target) {
				if (!cur->pre) { break; }
				cur = cur->pre;
				assert(cur != cur->pre);
			}
		}
		if (cur->value > target) {
			// 插入cur左侧
			pos->next = cur;
			pos->pre = cur->pre;
			cur->pre = pos;
			if (pos->pre) { pos->pre->next = pos; }
			if (cur == head[index]) { head[index] = pos; }
		} else {
			// 插入cur右侧
			pos->pre = cur;
			pos->next = cur->next;
			cur->next = pos;
			if (pos->next) { pos->next->pre = pos; }
		}
	}
	// 将pos从link上删除
	inline void link_del(int index, Pos* pos) {
		if (pos == head[index]) { head[index] = pos->next; }
		if (pos->pre) { pos->pre->next = pos->next; }
		if (pos->next) { pos->next->pre = pos->pre; }
		pos->pre = pos->next = NULL;
	}
	// 处理轴点在轴线上的移动
	inline void link_move(int index, Pos* pos, bool toRight) {
		int cur = pos->value;
		Pos* last = NULL;
		Node* owner = pos->owner;
		int range = owner->range;
		
		if (toRight) {
			// 数据变大，向右移动
			Pos* tmp = pos->next;
			if (!tmp || tmp->value >= cur) { return; }

			while (tmp && tmp->value < cur) {
				if (tmp->owner != owner && ((pos->type & POS_TYPE_MID) || (tmp->type & POS_TYPE_MID))) {
					check_neighbour(pos, tmp, range, true);
				}
				assert(tmp != tmp->next);
				last = tmp;
				tmp = tmp->next;
			}
			// 从原来的地方删除
			if (pos == head[index]) { head[index] = pos->next; }
			if (pos->pre) { pos->pre->next = pos->next; }
			if (pos->next) { pos->next->pre = pos->pre; }
			pos->pre = pos->next = NULL;

			if (!tmp) {
				// 追加到尾部
				last->next = pos;
				pos->pre = last;
			} else {
				// 加到tmp前
				pos->next = tmp;
				pos->pre = tmp->pre;
				if (pos->pre) { pos->pre->next = pos; }
				tmp->pre = pos;
			}
		} else {
			// 数据变小，向左移动
			Pos* tmp = pos->pre;
			if (!tmp || tmp->value <= cur) { return; }

			while (tmp && tmp->value > cur) {
				if (tmp->owner != owner && ((pos->type & POS_TYPE_MID) || (tmp->type & POS_TYPE_MID))) {
					check_neighbour(pos, tmp, range, false);
				}
				assert(tmp != tmp->next);
				last = tmp;
				tmp = tmp->next;
			}
			if (pos == head[index]) { head[index] = pos->next; }
			if (pos->pre) { pos->pre->next = pos->next; }
			if (pos->next) { pos->next->pre = pos->pre; }
			pos->pre = pos->next = NULL;

			if (!tmp) {
				// 追加到头部
				head[index] = pos;
				pos->next = last;
				last->pre = pos;
			} else {
				// 追加到tmp后面
				pos->pre = tmp;
				pos->next = tmp->next;
				if (pos->next) { pos->next->pre = pos; }
				tmp->next = pos;
			}
		}
	}

	// 将节点加到轴线上，index=0表示x轴
	inline void axis_add(int index, Node* node, int value) {
		// 初始化左右轴点，并将左右轴点串联
		int range = node->range;
		Pos* left = node->pos + index*3;
		Pos* mid = left + 1;
		Pos* right = left + 2;
		left->value = value - range;
		mid->value = value;
		right->value = value + range;

		Pos* cur = this->head[index];
		if (!cur) {
			// 直接将2个轴点按顺序挂到根节点上
			left->pre = NULL; left->next = mid;
			mid->pre = left; mid->next = right;
			right->pre = mid; right->next = NULL;
			this->head[index] = left;
			return;
		}

		// left: 插入到left-range后
		if (isFixedRange) {
			// 如果所有单位的视野是一致的，左边界点不需要从坐标轴最左侧插入
			link_add(index, left, value - range - range, cur);
		} else {
			// 如果所有单位的视野可能不一样，就需要从左边界点插入
			left->pre = NULL; left->next = cur;
			cur->pre = left;
			this->head[index] = left;
		}
		if (!left->next) {
			left->next = mid;
			mid->pre = left; mid->next = right;
			right->pre = mid; right->next = NULL;
			return;
		}
		link_move(index, left, true);

		// mid:
		cur = this->head[index];
		if (isFixedRange) {
			link_add(index, mid, value - range - range, left);
		} else {
			mid->pre = NULL; mid->next = cur;
			cur->pre = mid;
			this->head[index] = mid;
		}
		if (!mid->next) {
			mid->next = right;
			right->pre = mid;
			right->next = NULL;
			return;
		}
		link_move(index, mid, true);

		// right:
		cur = this->head[index];
		if (isFixedRange) {
			link_add(index, right, value - range - range, mid);
		} else {
			right->pre = NULL; right->next = cur;
			cur->pre = right;
			this->head[index] = right;
		}
		if (right->next) {
			right->next->pre = right;
			link_move(index, right, true);
		}
	}

	inline void axis_move(int index, Node* node, int offset) {
		bool toRight = offset >= 0;
		Pos* pos = node->pos + index + index + index;
		pos->value += offset;
		link_move(index, pos, toRight);
		pos++;
		pos->value += offset;
		link_move(index, pos, toRight);
		pos++;
		pos->value += offset;
		link_move(index, pos, toRight);
	}

	// 将节点从轴线上删除
	inline void axis_del(int index, Node* node) {
		Pos* pos = node->pos + index + index + index;
		link_del(index, pos + 2);
		link_del(index, pos + 1);
		link_del(index, pos);
	}

	void event(EnAoiEvent evt, uint32_t nodeId, NodeMap& nodeMap) {
		lua_getref(g_AoiLua, callback);
		if (!lua_isfunction(g_AoiLua, -1)) { return; }
		lua_pushinteger(g_AoiLua, id);
		lua_pushinteger(g_AoiLua, evt);
		lua_pushinteger(g_AoiLua, nodeId);
		// lua_pushnumber(g_AoiLua, id);
		// lua_pushnumber(g_AoiLua, evt);
		// lua_pushnumber(g_AoiLua, nodeId);
		lua_createtable(g_AoiLua, nodeMap.size(), 0);
		int index = 0;
		for (NodeMap::iterator it = nodeMap.begin(); it != nodeMap.end(); it++) {
			index++;
			lua_pushinteger(g_AoiLua, index);
			lua_pushinteger(g_AoiLua, it->first);
			// lua_pushnumber(g_AoiLua, index);
			// lua_pushnumber(g_AoiLua, it->first);
			lua_rawset(g_AoiLua, -3);
		}
		lua_pcall(g_AoiLua, 4, 0, 0);
	}

	int enter(uint32_t id, int range, int smask, int imask, int x, int y) {
		if (nodes.find(id) != nodes.end()) { return 0; }
		Node* node = CreateNode();
		if (node) {
			node->id = id;
			node->range = range;
			node->smask = smask;
			node->imask = imask;
			node->center[0] = x;
			node->center[1] = y;
		} else {
			node = new Node(id, range, smask, imask, x, y);
		}
		nodes.insert(NodeMap::value_type(id, node));
		axis_add(0, node, x);
		axis_add(1, node, y);
		
		// node进入fans的视野
		if (!node->fans.empty()) {
			event(EnAoiEvent::FansEnter, id, node->fans);
		}
		if (!node->mark.empty()) {
			event(EnAoiEvent::MarkEnter, id, node->mark);
		}
		return 1;
	}

	int leave(uint32_t id) {
		NodeMap::iterator it = nodes.find(id);
		if (it == nodes.end()) { return 0; }
		Node* node = it->second;
		nodes.erase(it);
		
		axis_del(0, node);
		axis_del(1, node);

		NodeMap& fans = node->fans;
		if (!fans.empty()) {
			node->clear_mark();
			event(EnAoiEvent::FansLeave, id, fans);
			fans.clear();
		}
		NodeMap& mark = node->mark;
		if (!mark.empty()) {
			node->clear_fans();
			event(EnAoiEvent::MarkLeave, id, mark);
			mark.clear();
		}
		ReleaseNode(node);
		return 1;
	}

	int move(uint32_t id, int x, int y) {
		NodeMap::iterator it = nodes.find(id);
		if (it == nodes.end()) { return 0; }
		Node* node = it->second;
		int oldX = node->center[0];
		int oldY = node->center[1];
		if (oldX == x && oldY == y) { return 1; }

		node->tmp[0].clear();
		node->tmp[1].clear();
		node->tmp[2].clear();
		node->tmp[3].clear();

		if (oldX != x) {
			node->center[0] = x;
			axis_move(0, node, x - oldX);
		}
		if (oldY != y) {
			node->center[1] = y;
			axis_move(1, node, y - oldY);
		}

		for (int i = 0; i < 4; i++) {
			NodeMap& nodeMap = node->tmp[i];
			if (!nodeMap.empty()) {
				event((EnAoiEvent)i, id, nodeMap);
				nodeMap.clear();
			}
		}
		return 1;
	}

};

static int l_aoi_enter(lua_State* L) {
	AOI_LOCK
	Scene* scene = (Scene*)lua_touserdata(L, 1);
	if (!scene) { return 0; }
	uint32_t id = (uint32_t)luaL_checknumber(L, 2);
	int range = (int)luaL_checknumber(L, 3);
	if (range <= 0) { return 0; }
	int smask = (int)luaL_checknumber(L, 4);
	int imask = (int)luaL_checknumber(L, 5);
	int x = (int)luaL_checknumber(L, 6);
	int y = (int)luaL_checknumber(L, 7);
	int ret = scene->enter(id, range, smask, imask, x, y);
	lua_pushboolean(L, ret);
	AOI_UNLOCK
	return 1;
}

static int l_aoi_leave(lua_State* L) {
	AOI_LOCK
	Scene* scene = (Scene*)lua_touserdata(L, 1);
	if (!scene) { return 0; }
	uint32_t id = (uint32_t)luaL_checknumber(L, 2);
	int ret = scene->leave(id);
	lua_pushboolean(L, ret);
	AOI_UNLOCK
	return 1;
}

static int l_aoi_move(lua_State* L) {
	AOI_LOCK
	Scene* scene = (Scene*)lua_touserdata(L, 1);
	if (!scene) { return 0; }
	uint32_t id = (uint32_t)luaL_checknumber(L, 2);
	int x = (int)luaL_checknumber(L, 3);
	int y = (int)luaL_checknumber(L, 4);
	int ret = scene->move(id, x, y);
	lua_pushboolean(L, ret);
	AOI_UNLOCK
	return 1;
}

static int l_aoi_fans_list(lua_State* L) {
	Scene* scene = (Scene*)lua_touserdata(L, 1);
	if (!scene) { return 0; }
	uint32_t id = (uint32_t)luaL_checknumber(L, 2);
	NodeMap& nodes = scene->nodes;
	NodeMap::iterator it = nodes.find(id);
	if (it == nodes.end()) { return 0; }
	Node* node = it->second;
	NodeMap& nodeMap = node->fans;
	lua_createtable(L, nodeMap.size(), 0);
	int index = 0;
	for (it = nodeMap.begin(); it != nodeMap.end(); it++) {
		index++;
		lua_pushnumber(L, index);
		lua_pushnumber(L, it->first);
		lua_rawset(L, -3);
	}
	return 1;
}

static int l_aoi_mark_list(lua_State* L) {
	Scene* scene = (Scene*)lua_touserdata(L, 1);
	if (!scene) { return 0; }
	uint32_t id = (uint32_t)luaL_checknumber(L, 2);
	NodeMap& nodes = scene->nodes;
	NodeMap::iterator it = nodes.find(id);
	if (it == nodes.end()) { return 0; }
	Node* node = it->second;
	NodeMap& nodeMap = node->mark;
	lua_createtable(L, nodeMap.size(), 0);
	int index = 0;
	for (it = nodeMap.begin(); it != nodeMap.end(); it++) {
		index++;
		lua_pushnumber(L, index);
		lua_pushnumber(L, it->first);
		lua_rawset(L, -3);
	}
	return 1;
}

static int l_aoi_gc(lua_State* L) {
	Scene* scene = (Scene*)lua_touserdata(L, -1);
	scene->~Scene();
	return 0;
}

int l_aoi_create(lua_State* L) {
	g_AoiLua = L;
	uint32_t id = (uint32_t)luaL_checknumber(L, 1);
	bool isFixedRange = lua_toboolean(L, 2);
	if (!lua_isfunction(L, 3)) {
		lua_pushnil(L);
		lua_pushstring(L, "param3 need function for OnAoiEvent");
		return 2;
	}
	
	lua_pushvalue(L, 3);
	int callback = luaL_ref(L, LUA_REGISTRYINDEX);

	void* scene = lua_newuserdata(L, sizeof(Scene));
	if (luaL_newmetatable(L, "meta_aoi")) {
		const luaL_Reg meta[] = {
			{ "enter", l_aoi_enter },
			{ "leave", l_aoi_leave },
			{ "move", l_aoi_move },
			{ "fans_list", l_aoi_fans_list },
			{ "mark_list", l_aoi_mark_list },
			{ NULL, NULL },
		};
		luaL_register(L, "meta_aoi", meta);
		lua_setfield(L, -2, "__index");

		lua_pushcfunction(L, l_aoi_gc);
		lua_setfield(L, -2, "__gc");
	}
	lua_setmetatable(L, -2);
	
	new(scene) Scene(id, callback, isFixedRange);
	return 1;
}

int l_aoi_release(lua_State* L) {
	// print_stat();
	ReleaseAllNode();
	return 0;
}

// int call_luafunc(lua_State* L){
// 	int a = lua_tointeger(L, 1);
// 	// lua_pushcfunction(L, stackdump); //error func
// 	// lua_pushvalue(L, 2); // lua func

// 	{
// 		lua_pushcfunction(L, stackdump); //error func
// 		lua_pushvalue(L, 2); // lua func
// 		lua_pushinteger(L, a);
// 		int code = lua_pcall(L, 1, 0, -3);
// 		if (code == 0){
// 			printf("执行成功\n");
// 		}else
// 		{
// 			printf("执行错误\n");
// 		}
// 	}
// 	return 0;
// }
